Un albero di copertura (spanning tree) in un grafo è un sottoinsieme di archi che connette tutti i vertici del grafo senza formare cicli. Il termine "spanning tree" si riferisce al fatto che l'albero "spazia" su tutti i vertici del grafo come un albero di copertura.
In un grafo non orientato e connesso, esiste sempre almeno un albero di copertura chiamato albero di copertura minimo (minimum spanning tree). Il problema di trovare un minimum spanning tree è di grande importanza pratica in molte applicazioni, come reti di comunicazione, reti stradali, distribuzione di energia e altro ancora.
L'algoritmo più noto per trovare un minimum spanning tree è l'algoritmo di Kruskal e l'algoritmo di Prim. Entrambi gli algoritmi utilizzano la tecnica dell'algoritmo greedy per trovare un minimum spanning tree in modo efficiente.
Un'altra applicazione importante degli spanning tree è nell'algoritmo di broadcast in una rete di computer, dove l'albero di copertura è utilizzato per instradare in modo efficiente i messaggi a tutti i nodi della rete.
Ne Demek sitesindeki bilgiler kullanıcılar vasıtasıyla veya otomatik oluşturulmuştur. Buradaki bilgilerin doğru olduğu garanti edilmez. Düzeltilmesi gereken bilgi olduğunu düşünüyorsanız bizimle iletişime geçiniz. Her türlü görüş, destek ve önerileriniz için iletisim@nedemek.page